package SwordFingerOffer;

public class Q51_ReversePair {
    //统计数组中的逆序对 ==> HARD
    //逆序对定义:
    //在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对
    //解决方案 ==> 在归并排序框架中收集答案

    //逆序对数目
    public static int count = 0;

    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        // ==> 反 OJ 缓存机制
       count = 0;
       process(nums, 0, nums.length - 1);
       return count;
    }

    //
    public void process(int[] nums, int L, int R) {
        //base case
        //只有一个元素天然有序
        if (L == R){
            return;
        }
        //中点
        int M = L + ((R - L) >> 1);
        //左边有序
        process(nums, L, M);
        //右边有序
        process(nums, M + 1, R);
        //整体有序
        merge(nums, M, L, R);
    }


    //核心就是 merge 方法
    //合并两个有序数组 ==> 让整体有序
    public void merge(int[] arr, int M, int L, int R){

        int[] tmp = new int[R - L + 1];
        //左右指针
        int left = L;
        int right = M + 1;
        int index = 0;
        while (left != M + 1 && right != R + 1){
            //在这里插入相关操作
            //我比你大 那我后面的也肯定比你大
            if (arr[left] > arr[right])
                count += M - left + 1;
            tmp[index++] = arr[left] < arr[right] ? arr[left++] : arr[right++];

        }
        //补齐的时候也要考虑我们的结果

        //左边没指完 ==> 左边剩下的比右边的都大
        while (left != M + 1){
            //每个没指完的产生右边个逆序对
//            count += (right - M + 1);
            tmp[index++] = arr[left++];
        }
        while (right != R + 1){
            tmp[index++] = arr[right++];
        }
        //打回原数组
        for (int i = 0; i < tmp.length; i++) {
            arr[L + i] = tmp[i];
        }
    }

    public static void main(String[] args) {
        Q51_ReversePair fun = new Q51_ReversePair();
        System.out.println(fun.reversePairs(new int[]{4,5,6,7}));
    }
}
